# 字符串相乘：https://leetcode-cn.com/problems/multiply-strings/
# 直接模拟
class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        """
            直接模拟：
            rst = '0' 代表最后结果
            num1 与 num2 的每一位进行相乘，赋值给临时变量 temp， 所有temp 相加就是最终结果。   所以 rst += temp
            1. 计算一个temp
            2. rst += temp 直到结束
        """
        # 如果任意方为 0， 直接结束
        if num1 == "0" or num2 == "0":
            return "0"

        rst = '0'
        # 循环遍历num2每一个数
        for i in range(len(num2)-1, -1 , -1):
            # 计算num1 和 num2的一位相乘
            carry = 0
            index = len(num1) - 1
            num = ord(num2[i]) - ord("0")
            # 如果这个数字是0，那么就没有必要进行计算，一个是节省时间，第二个是例如 "9133" 和 "0"，得到 "0000"是错误的结
            if num == 0: continue
            # 举例子这个数表示百位的数的话，就要在后面拼接上 00
            temp = '0' * (len(num2) - i - 1)

            # 开始计算乘： temp
            while index >= 0:
                dig = ord(num1[index]) - ord("0")
                sum1 = dig * num + carry
                temp = str(sum1 % 10) + temp
                carry = sum1 // 10
                index -= 1

            if carry != 0: temp = str(carry) + temp; carry = 0

            # 乘的结果，加到结果字符串里 rst += temp
            rst_i, temp_i = len(rst) - 1, len(temp) - 1
            temp_1 = ''
            while rst_i >= 0 or temp_i >= 0:
                dig1 = ord(rst[rst_i]) - ord("0") if rst_i >= 0 else 0
                dig2 = ord(temp[temp_i]) - ord("0") if temp_i >= 0 else 0

                sum2 = dig1 + dig2 + carry
                temp_1 = str(sum2 % 10) + temp_1
                carry = sum2 // 10
                rst_i -= 1; temp_i -= 1
                
            if carry != 0: temp_1 = str(carry) + temp_1
            # 临时结果再保存给 rst
            rst = temp_1
        
        return rst


# 优化写法
class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        """
            改进版， 不需要将相乘的结果，累加进结果字符串，对字符串的操作太耗时了
            我们直接定义出结果列表。 让 num1 num2的每一位进行相乘，乘得结果直接写入到数组中。（这个数组表示超大的数，每个元素是这个数的一位）最后计算完毕，再把数组转换为 字符串。
        """
        if num1 == "0" or num2 == "0":
            return "0"
        
        m, n = len(num1), len(num2)
        res = [0] * (m + n)
        for i in range(m - 1, -1, -1):
            x = int(num1[i])
            for j in range(n - 1, -1, -1):
                y = int(num2[j])
                sum = res[i + j + 1] + x * y
                res[i + j + 1] = sum % 10
                res[i + j] += sum // 10
    
        index = 1 if res[0] == 0 else 0
        ans = "".join(str(x) for x in res[index:])
        return ans



num1 = "123"
num2 = "456"
s = Solution()
rst = s.multiply(num1, num2)
print(rst)



